In recent years, as a result of advances in digital computers/cameras, image-processing algorithms have been widely used in applications including medical imaging, security and surveillance, navigation, multimedia and quality inspection. Many of these applications are used in real-time systems (with both soft and hard time constraints) where it is crucial to meet certain performance requirements. On the other hand, image-processing algorithms are usually computationally expensive.
Traditionally, software running on microprocessors and digital signal processors has provided adequate computational power to cope with the real-time image processing challenges, namely providing the results in real time. Nevertheless, as image resolution, complexity of algorithms, and the difficulty of the tasks increase, the conventional approaches of software implementations of image processing algorithms are increasingly unable to overcome these obstacles.
A common solution to meet the performance requirements of real-time image processing is to embed these algorithms in specialized digital hardware platforms (i.e. FPGA and ASIC). However, hardware design is more difficult and time consuming than coding software. Thus, in situations where a long time to market is not a viable option, the hardware approach may not be feasible. In addition, the specialized hardware approach usually involves significant capital investment to “re-tool” the manufacturing process to implement new hardware within the target device.
Currently, the machine vision and image processing end-product market is dominated by soft and hard real-time applications where it is imperative to meet the performance requirements. In hard real-time applications, such as a visual based vehicle navigation system, it may be fatal not to be able to process the incoming images quickly enough. In soft real-time systems, such as magnetic resonance imaging (MRI), although it is not fatal not to have a high-performance system, it is however important to increase the speed of the computations to enable greater patient throughput and, consequently, greater patient access to MRI-based diagnostics.
It is clear that improving performance for image processing applications has significant merit. Meanwhile, the general concept of memoization in computer programs has been around for a long time. Memoization is the idea to speed up computer programs by avoiding function calls that repeat the calculation of results for already processed inputs. Nevertheless, in practice, the general notion of memoization has not gained success due to the following reasons: 1) in software, the proposed techniques usually require detailed profiling information about the runtime behavior of the program which makes it difficult to implement, 2) in hardware, the memoization techniques have been mainly applied to processor design where the complexity of control circuitry and datapath makes it extremely difficult to benefit from reusing the results, and 3) the proposed techniques are usually generic methods which do not concentrate on any particular class of input data or algorithms. This significantly limits the overall performance improvement in both software and hardware.
What is required, therefore, is a means that is customized to image data and by which to implement memoization for image processing algorithms (in software) without the need to provide detailed profiling information about the runtime behavior of the program and to apply memoization to image processing algorithms implemented in digital hardware platforms (e.g. FPGA).